home *** CD-ROM | disk | FTP | other *** search
/ Atari Mega Archive 1 / Atari Mega Archive - Volume 1.iso / archiver / lzhsourc.lzh / LZH.SRC / LZST.S < prev    next >
Text File  |  1992-07-02  |  7KB  |  214 lines
  1. N               equ 4096
  2. F               equ 18
  3. THRESHOLD       equ 2
  4. NIL             equ $1000
  5.  
  6.                 import  match_length
  7.                 import  last_mat
  8.                 import  printcou
  9.                 import  textsize
  10.                 import  code_buf
  11.                 import  text_buf
  12.                 import  infile
  13.                 import  outfile
  14.  
  15.                 import  InitTree
  16.                 import  fgetc
  17.                 import  match_position
  18.                 import  fputc
  19.                 import  _StdOutF
  20.                 import  codesize
  21.  
  22.                 import    dad
  23.                 import    lson
  24.                 import    rson
  25.                 export  Encode
  26.                 export  InsertONode
  27.                 export  DeleteONode
  28. DeleteONode:    movem.l D0-A6,-(SP)
  29.                 lea     lson,A2
  30.                 lea     rson,A3
  31.                 move.w  D0,D5
  32.                 move.w  #2*NIL,D7
  33.                 lea     dad,A0
  34.                 add.w   D5,D5
  35. ; if dad[p] == NIL
  36.                 cmp.w   0(A0,D5.w),D7
  37.                 beq.b   DNode_9
  38. ; if rson[p] == NIL
  39.                 cmp.w   0(A3,D5.w),D7
  40.                 beq.b   DNodex1
  41.  
  42. ; if lson[p] == NIL
  43. DNode_1:        cmp.w   0(A2,D5.w),D7
  44.                 beq.b   DNodex2
  45.  
  46. DNode_2:        lea     0(A2,D5.w),A4   ; lson[p]
  47.                 lea     0(A3,D5.w),A5   ; rson[p]
  48.                 move.w  (A4),D1
  49.  
  50.                 move.w  D1,D2
  51.                 cmp.w   0(A3,D2.w),D7
  52.                 beq.b   DNode_5
  53. ; do { q=rson[q] } while (rson[q] != NIL}
  54.  
  55. DNode_3:        move.w  0(A3,D2.w),D2
  56.                 cmp.w   D7,D2
  57.                 beq.b   DNode_4
  58.                 move.w  D2,D1
  59.                 bra.b   DNode_3
  60.  
  61. DNode_4:        move.w  D1,D2
  62.                 move.w  0(A0,D2.w),D3
  63.                 lea     0(A2,D2.w),A1   ; rson[q]
  64.                 move.w  (A1),0(A3,D3.w) ; lson[dad[q]] = rson[q]
  65.                 move.w  (A1),D3
  66.                 move.w  0(A0,D2.w),0(A0,D3.w) ; dad[rson[q]]=dad[q[
  67.                 move.w  (A4),D3
  68.                 move.w  D3,(A1)         ; rson[q]=rson[p]
  69.                 move.w  D1,0(A0,D3.w)
  70. DNode_5:        move.w  (A5),D3
  71.                 move.w  D3,0(A3,D2.w)   ; rson[q] = rson[p]
  72.                 move.w  D1,0(A0,D3.w)   ; dad[rson[p]] = q
  73. DNode_6:        move.w  0(A0,D5.w),0(A0,D1.w) ; dad[q]=dad[p]
  74.  
  75.                 lea     0(A0,D5.w),A5   ; A5=*dad[p]
  76.                 move.w  (A5),D3         ; D3 = cardinal dad[p]
  77.                 cmp.w   0(A3,D3.w),D5
  78.                 bne.b   DNode_7         ; if rson[dad[p]]=p
  79. ; else ..
  80.                 move.w  D1,0(A3,D3.w)   ; rson[dad[p]]=q
  81.                 move.w  D7,(A5)
  82.                 movem.l (SP)+,D0-A6
  83.                 rts
  84. ; if ..
  85. DNode_7:        move.w  D1,0(A2,D3.w)   ; lson[dad[p]]=q
  86. ; endif ..
  87. DNode_8:        move.w  D7,(A5)         ; dad[p]=NIL
  88. DNode_9:        movem.l (SP)+,D0-A6
  89.                 rts
  90. DNodex2:        move.w  0(A3,D5.w),D1
  91.                 bra.b   DNode_6
  92. DNodex1:        move.w  0(A2,D5.w),D1
  93.                 bra.b   DNode_6
  94. ; void InsertNode(int r);
  95. ; rester int i,p,cmp;
  96. ; unsigned char *key;
  97. ; unigned c;
  98.  
  99. ; register D1 = cmp
  100. ; register D2 = p
  101. ; register A1 = *key
  102. ; register A2 = rson
  103. ; register A3 = lson
  104.  
  105. ; D0 = cardinal p
  106.  
  107. ; Benötigt: A0 = text_buf
  108. ;           A2 = lson
  109. ;           A3 = rson
  110. ;           A4 = dad
  111.  
  112.                 lea     lson,A2
  113.                 lea     rson,A3
  114.                 lea     text_buf,a5
  115. InsertONode:    movem.l D0-A6,-(SP)
  116.                 lea     lson,A2
  117.                 lea     rson,A3
  118.                 lea     text_buf,a5
  119.  
  120.                 move.w  D0,D6
  121.                 moveq   #1,D1           ; cmp=1
  122.  
  123.                 lea     0(A5,D6.w),A1   ; key=&text_buf[r]
  124.                 add.w   D6,D6
  125.  
  126.                 moveq   #0,D2
  127.                 move.b  (A1),D2         ; key[0]
  128.                 add.w   #4097,D2        ; p= N+1+key[0]
  129.                 add.w   D2,D2           ; cardinal
  130.  
  131.                 move.w  #2*NIL,D7       ; NIL
  132.                 move.w  D7,0(A2,D6.w)   ; rson[r] = NIL
  133.                 move.w  D7,0(A3,D6.w)   ; lson[r] = NIL
  134.  
  135.                 clr.w   match_length    ; match_length=0
  136. ; for ...
  137.                 lea     dad,A4
  138. I_Node1:        tst.w   D1              ; if (cmp > 0) {
  139.                 blt.b   I_Node4
  140.                 lea     0(A3,D2.w),A6   ; rson[p]
  141.                 cmp.w   (A6),D7         ; if rson[p] != NIL
  142.                 bne.b   I_Node5         ; p=rson[p] else
  143.  
  144. I_Node2:        move.w  D6,(A6)         ; rson[p] = r
  145.                 move.w  D2,0(A4,D6.w)   ; dad[r] = p
  146.                 bra     I_Node11
  147.  
  148. I_Node3:        move.w  D6,(A6)         ; lson[p] = r
  149.                 move.w  D2,0(A4,D6.w)   ; dad[r] = p
  150.                 bra     I_Node11
  151.  
  152. I_Node4:        lea     0(A2,D2.w),A6   ; d7=lson[p]
  153.                 cmp.w   (A6),D7         ; if lson[p] != NIL
  154.                 beq.b   I_Node3
  155.  
  156. ; for (i=1; i<F; i++)
  157. I_Node5:        move.w  (A6),D2
  158.                 moveq   #0,D1
  159.                 moveq   #F-2,D5
  160.                 lea     1(A1),A0        ; key[1]
  161.                 lsr.w   #1,D2
  162.                 lea     1(A5,D2.w),A6   ; text_buf[p+1]
  163.                 add.w   D2,D2
  164. I_Node6:        cmpm.b  (A0)+,(A6)+
  165.                 dbne    D5,I_Node6
  166.  
  167. I_Node7:        moveq   #F-1,D3
  168.                 sub.w   D5,D3
  169.                 moveq   #0,D5
  170.                 move.b  -1(A0),D1
  171.                 move.b  -1(A6),D5
  172.                 sub.w   D5,D1           ; d1=key[i]-text_buf[p+i]
  173.  
  174.                 lea     match_length,A6
  175.                 cmp.w   (A6),D3         ; if i>match_length
  176.                 ble.b   I_Node1
  177.  
  178.                 move.w  D2,D4
  179.                 lsr.w   #1,D4
  180.                 move.w  D4,match_position
  181.  
  182.                 move.w  D3,(A6)         ; match_length=i
  183.                 cmp.w   #F,D3           ; if i>=F
  184.                 blt.b   I_Node1         ; break
  185.  
  186. ;  break
  187. I_Node8:        move.w  0(A4,D2.w),0(A4,D6.w) ; dad[r] = dad[p]
  188.                 move.w  0(A2,D2.w),0(A2,D6.w) ; lson[r] = lson[p]
  189.                 move.w  0(A3,D2.w),0(A3,D6.w) ; rson[r] = rson[p[
  190.  
  191.                 move.w  0(A2,D2.w),D4
  192.                 move.w  D6,0(A4,D4.w)   ; dad[lson[p]]=r
  193.  
  194.                 move.w  0(A3,D2.w),D4
  195.                 move.w  D6,0(A4,D4.w)   ; dad[rson[p]]=r
  196.  
  197.                 lea     0(A4,D2.w),A6
  198.                 move.w  (A6),D4         ; a6 = *dat[p]
  199.                 cmp.w   0(A3,D4.w),D2
  200.                 beq.b   I_Node12
  201.  
  202. I_Node9:        move.w  (A6),D3
  203.                 move.w  D6,0(A2,D3.w)   ; lson[dad[p]] = r
  204.  
  205. I_Node10:       move.w  D7,(A6)         ; dad[p] = NIL
  206. I_Node11:       movem.l (SP)+,D0-A6
  207.                 rts
  208.  
  209. I_Node12:       move.w  D6,0(A3,D4.w)
  210.                 move.w  D7,(A6)         ; dad[p] = NIL
  211.                 movem.l (SP)+,D0-A6
  212.                 rts
  213.                 end
  214.